package com.example.common.util;

import java.util.Arrays;

/**
 * @author Aaron
 * @date 2021/11/4 13:03
 * @description 排序
 */
public class SortUtil {

    public static void main(String[] args) {
        Integer[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        System.out.println("----" + Arrays.toString(arr));

        System.out.println("\n--------------");

        Integer[] sort = BubbleSort.sort(arr);
        Arrays.stream(sort).forEach(System.out::print);

        System.out.println("\n--------------");
        Integer[] sort2 = QuickSort.sort(arr);
        System.out.println("----" + Arrays.toString(sort2));
    }

    /**
     * 冒泡
     */
    public static class BubbleSort {
        public static <T extends Comparable<T>> T[] sort(T[] srcArray) {
            T[] array = Arrays.copyOf(srcArray, srcArray.length);

            for (int i = 0; i < array.length; i++) {
                for (int j = i + 1; j < array.length; j++) {
                    if (array[i].compareTo(array[j]) > 0) {
                        T t = array[i];
                        array[i] = array[j];
                        array[j] = t;
                    }
                }
            }
            return array;
        }
    }

    /**
     * 快速
     */
    public static class QuickSort {

        public static <T extends Comparable<T>> T[] sort(T[] srcArray) {
            T[] array = Arrays.copyOf(srcArray, srcArray.length);
            quickSort(array, 0, array.length - 1);
            return array;
        }

        public static <T extends Comparable<T>> void quickSort(T[] srcArray, int left, int right) {
            if (left >= right) {
                return;
            }

            // 以 left 元素为基准，index 表示比较后更换位置的左侧数据最后一个元素
            int index = left + 1;
            for (int i = index; i <= right; i++) {
                // 比较基准和第一个元素，如果小于基准，则更换 index 位置
                if (srcArray[left].compareTo(srcArray[i]) > 0) {
                    T t = srcArray[i];
                    srcArray[i] = srcArray[index];
                    srcArray[index] = t;
                    index++;
                }
            }

            // 交换 index 与 left 所在位置元素
            T t = srcArray[index - 1];
            srcArray[index - 1] = srcArray[left];
            srcArray[left] = t;

            quickSort(srcArray, left, index - 1 - 1);
            quickSort(srcArray, index, right);
        }


    }

}